package org.xingole.leetcode.dp.multidimension.jump;

import java.util.Arrays;

/**
 * Problem Description:
 * 
 * <a href="https://leetcode.com/problems/minimum-sideway-jumps/">
 * Minimum Sideway Jumps</a>
 */
public class MinimumSidewayJumps {
     private static final int POS_INF = 0x3f_ff_ff_ff;

     public int minSideJumps(int[] obstacles) {
          return minSideJumpsWithDP(obstacles);
     }

     private int minSideJumpsWithDP(int[] obstacles) {
          int nplusOne = obstacles.length;
          // 1. Determine the subproblem substructure.
          // Let dp[i][j] represents the minimum number of side jumps the frog needs 
          // to reach the j-th lane at point i from lane 2 at point 0.

          // we only consider 0 <= i <= n and 1 <= j <= 3.
          int[][] dp = new int[nplusOne][4];

          // 2. Recursively solve the problem
          //    - Base Case:
          //      dp[0][2] = 0;
          //      dp[0][j] = 1, for j = 1, 3
          //    - Inductive Case:
          //      if obstacle[i] != j, then 
          //         dp[i][j] = min(dp[i-1][j], dp[i][k] + 1)
          //      where k != j and obstacles[j] != k.
          //      otherwise,
          //         dp[i][j] = +infinity
          Arrays.fill(dp[0], 1, 4, 1);

          dp[0][2] = 0;
          for ( int i = 1; i < nplusOne; i++ ) {
               // For loop iteration, we can have more technique to 
               // do the programming.
               
               // partition two loops to calculate the minimum sideway jumps,
               // to decrease the time complexity.
               int minJumps = POS_INF;
               for ( int j = 1; j <= 3; j++ ) {

                    if ( obstacles[i] == j ) {
                         dp[i][j] = POS_INF;
                    } else {
                         dp[i][j] = dp[i-1][j];
                    }

                    minJumps = Math.min(minJumps, dp[i][j]);
               }

               // If all horizon movement is impossible, the dp[i][j] must be +infinity.
               // we can assert that minJumps << +infinity/
               for ( int j = 1; j <= 3; j++ ) {
                    if ( obstacles[i] == j ) {
                         continue;
                    }

                    dp[i][j] = Math.min(dp[i][j], minJumps + 1);
               }

          }

          return Math.min(Math.min(dp[nplusOne-1][1], dp[nplusOne - 1][2]), dp[nplusOne - 1][3]);
     }

}
